<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>八皇后问题</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="八皇后问题">八皇后问题</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=xouin83ebxE&amp;list=PLrmLmBdmIlpuE5GEMDXWf0PWbBD9Ga1lO&amp;index=5">https://www.youtube.com/watch?v=xouin83ebxE&amp;list=PLrmLmBdmIlpuE5GEMDXWf0PWbBD9Ga1lO&amp;index=5</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/NQueenProblem.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/NQueenProblem.java</a></li>
</ul>
<p>LC 51. N-Queens</p>
<ul>
<li><a href="https://leetcode.com/problems/n-queens/">https://leetcode.com/problems/n-queens/</a></li>
</ul>
<h1 id="v1-版本会超时">v1 版本，会超时</h1>
<p>下面有2个错误。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">solveNQueens</span><span class="hljs-params">(self, n: int)</span> -&gt; List[List[str]]:</span>
        ans = []
        matrix = [[<span class="hljs-string">"."</span>] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)]
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_valid</span><span class="hljs-params">(matrix, i, j, n)</span>:</span>
            <span class="hljs-comment"># check row                  # 第一个错误，没必要检查row了。我们本来就是按row遍历的</span>
            <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> matrix[i][k] == <span class="hljs-string">"Q"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
                
            <span class="hljs-comment"># check column</span>
            <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> matrix[k][j] == <span class="hljs-string">"Q"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
                
            <span class="hljs-comment"># positions[j].col - positions[j].row == i - current </span>
            l = j - i
            <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(n-l):
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span>&lt;=k&lt;n <span class="hljs-keyword">and</span> <span class="hljs-number">0</span>&lt;=k+l&lt;n <span class="hljs-keyword">and</span> matrix[k][k+l] == <span class="hljs-string">"Q"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            
            <span class="hljs-comment"># positions[j].row + positions[j].col == i + current</span>
            l = i + j - n
            <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span>&lt;=k&lt;n <span class="hljs-keyword">and</span> <span class="hljs-number">0</span>&lt;=n+l-k&lt;n <span class="hljs-keyword">and</span> matrix[k][n+l-k] == <span class="hljs-string">"Q"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
                
            
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(matrix, s_row, n)</span>:</span>
            <span class="hljs-keyword">if</span> s_row == n:
                t = []
                <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> matrix:
                    t.append(<span class="hljs-string">""</span>.join(r))
                ans.append(t)
                <span class="hljs-keyword">return</span>
            
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(s_row, n):      <span class="hljs-comment"># 第二个错误，导致超时。</span>
                <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
                    <span class="hljs-keyword">if</span> _valid(matrix, i, j, n):
                        matrix[i][j] = <span class="hljs-string">'Q'</span>
                        _helper(matrix, s_row+<span class="hljs-number">1</span>, n)
                        matrix[i][j] = <span class="hljs-string">"."</span>
            
        _helper(matrix, <span class="hljs-number">0</span>, n)
        <span class="hljs-keyword">return</span> ans

</div></code></pre>
<h1 id="v2-版本">v2 版本</h1>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> copy <span class="hljs-keyword">import</span> deepcopy
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">solveNQueens</span><span class="hljs-params">(self, n: int)</span> -&gt; List[List[str]]:</span>

        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(row, n, board, r)</span>:</span>
            <span class="hljs-keyword">if</span> row &gt;= n:
                r2 = []
                <span class="hljs-keyword">for</span> row <span class="hljs-keyword">in</span> board:
                    r2.append(<span class="hljs-string">""</span>.join(row))
                r.append(r2)
                <span class="hljs-keyword">return</span>
            <span class="hljs-keyword">for</span> col <span class="hljs-keyword">in</span> range(n):
                board[row][col] = <span class="hljs-string">"Q"</span>
                <span class="hljs-keyword">if</span> is_valid(row, col, n, board):
                    _helper(row+<span class="hljs-number">1</span>, n, board, r)
                board[row][col] = <span class="hljs-string">"."</span>
                
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">is_valid</span><span class="hljs-params">(row, col, n, board)</span>:</span>
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(row):
                <span class="hljs-keyword">if</span> board[i][col] == <span class="hljs-string">"Q"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            i = <span class="hljs-number">1</span>
            <span class="hljs-keyword">while</span> row-i&gt;=<span class="hljs-number">0</span> <span class="hljs-keyword">and</span> col+i&lt;n:
                <span class="hljs-keyword">if</span> board[row-i][col+i] == <span class="hljs-string">"Q"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
                i += <span class="hljs-number">1</span>
            
            i = <span class="hljs-number">1</span>
            <span class="hljs-keyword">while</span> row-i&gt;=<span class="hljs-number">0</span> <span class="hljs-keyword">and</span> col-i&gt;=<span class="hljs-number">0</span>:
                <span class="hljs-keyword">if</span> board[row-i][col-i] == <span class="hljs-string">"Q"</span>:
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
                i += <span class="hljs-number">1</span>
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        
        board = [[<span class="hljs-string">"."</span>] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)]
        r = []
        _helper(<span class="hljs-number">0</span>, n, board, r)
        <span class="hljs-keyword">return</span> r
</div></code></pre>
<h1 id="v3-tushare-roy版本">v3 tushare roy版本</h1>
<ul>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/NQueenProblem.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/NQueenProblem.java</a></li>
</ul>
<p>tushare的版本有一个比较好的地方，就是递归遍历的时候，记录了已知的所有Q位置，那么判断下一个位置是否能放Q的时候，只需要和已知的所有Q位置比较即可。
而不用像前面v1, v2版本那样去遍历。</p>

    </body>
    </html>